package leetcode;

import java.util.*;

public class LeetCodeMain82 {
    int num=0;
    HashMap<Integer,Integer> map=new HashMap<>();
    List<Integer> list=new LinkedList<>();
    public LeetCodeMain82(int capacity) {
        num=capacity;
    }

    public int get(int key) {
        int index=list.indexOf(key);
        if (index>=0){
            list.remove(index);
            list.add(key);
            return map.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        int index=list.indexOf(key);
        if (index>=0){
            list.remove(index);
            list.add(key);
            map.put(key,value);
        }else {
            if (map.size()>=num){
                int key1=list.get(0);
                list.remove(0);
                list.add(key);
                map.remove(key1);
                map.put(key,value);
            }else {
                list.add(key);
                map.put(key,value);
            }
        }
    }



    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>(((o1, o2) -> o2-o1));
        for (int num:nums) {
            queue.add(num);
        }
        int count=0;
        while (!queue.isEmpty()){
            count++;
            int num=queue.poll();
            if (count==k){
                return num;
            }
        }
        return -1;
    }
    public int maxProduct(int[] nums) {
        int length=nums.length;
        int max=Integer.MIN_VALUE;
        int max2=1;
        int min=1;
        for (int i = 0; i < length; i++) {
            if (nums[i]<0){
                int tmp=max2;
                max2=min;
                min=tmp;
            }
            min=Math.min(nums[i],min*nums[i]);
            max2=Math.max(nums[i],max2*nums[i]);
            max=Math.max(max,max2);
        }
        return max;
    }
    public int[] dailyTemperatures(int[] temperatures) {
        int length=temperatures.length;
        int[] dp=new int[length];
        for (int i = 0; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                if (temperatures[j]>temperatures[i]){
                    dp[i]=j-i;
                    break;
                }
            }
        }
        return dp;
    }
    Stack<Integer> stack=null;
    Stack<Integer> minStackk=null;
    public LeetCodeMain82() {
        stack=new Stack<>();
        minStackk=new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStackk.isEmpty()){
            minStackk.push(val);
        }else {
            if (minStackk.peek()>=val){
                minStackk.push(val);
            }
        }
    }

    public void pop() {
        int val=stack.pop();
        if (!minStackk.isEmpty()&&val==minStackk.peek()){
            minStackk.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStackk.peek();
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        long[] dp=new long[21];
        dp[2]=1;
        dp[3]=2;
        for (int i = 4; i <= 20; i++) {
            dp[i]=(i-1)*(dp[i-1]+dp[i-2]);
        }
        while (in.hasNext()){
            int n=in.nextInt();

            System.out.println(dp[n]);
        }
    }
    public static void main1(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int n=in.nextInt();
            int[] arr=new int[n];
            for (int i = 0; i < n; i++) {
                arr[i]=in.nextInt();
            }
            int[] dp=new int[n];
            Arrays.fill(dp,1);
            int max=0;
            for (int i = 0; i < n; i++) {
                for (int j = i-1; j >= 0; j--) {
                    if (arr[i]>arr[j]&&dp[i]<dp[j]+1){
                        dp[i]=dp[j]+1;
                    }
                }max=Math.max(dp[i],max);
            }
            System.out.println(max);
        }
    }
}
